"""
一个使用Dijkstra算法（动态规划）的路径规划器。
它被设计用来在网格迷宫中，寻找一条终点必须是EXIT、不包含回路的、
可以获得最高分数的路径，但是因为不包含回路，所以效果往往不理想
"""
import heapq
from config import *
from typing import Tuple, List, Dict
import numpy as np

class DPPlannerDijkstra:
    def __init__(self, maze_grid):
        """
        初始化规划器。
        :param maze_grid: 代表迷宫的数组。
        """
        self.maze = maze_grid
        self.rows, self.cols = maze_grid.shape

        self.base_value_map = {
            GOLD: 5, TRAP: -3, PATH: 0, START: 0,
            EXIT: 0, BOSS: 0
        }
        self.exit_bonus = 10
    # 找起点
    def get_start_pos(self):
        start_pos = None
        for r in range(self.rows):
            for c in range(self.cols):
                if self.maze[r, c] == START:
                    start_pos = (r, c)
        return start_pos

    def calculate_optimal_path(self) -> Tuple[List[Tuple[int, int]], float]:
        """
        使用Dijkstra算法计算终点为EXIT的无回路最高分路径。
        """
        value_map = self.base_value_map.copy()
        # 找起点
        start_pos = self.get_start_pos()
        assert start_pos, f"地图生成部分有问题，找不到起点"

        dp_scores = np.full((self.rows, self.cols), -float('inf'), dtype=float)
        predecessors = {}

        start_score = value_map.get(self.maze[start_pos], 0)
        pq = [(-start_score, start_pos, {start_pos})]

        dp_scores[start_pos] = start_score
        predecessors[start_pos] = None

        while pq:
            # 取出当前最高分的节点
            neg_score, (r, c), visited_path = heapq.heappop(pq)
            current_score = -neg_score

            if current_score < dp_scores[r, c]:
                continue

            for dr in [-1, 0, 1]:
                for dc in [-1, 0, 1]:
                    if dr == 0 and dc == 0: continue
                    nr, nc = r + dr, c + dc

                    if not (0 <= nr < self.rows and 0 <= nc < self.cols and self.maze[nr, nc] != WALL):
                        continue

                    neighbor = (nr, nc)
                    if neighbor in visited_path: continue
                    new_score = current_score + value_map.get(self.maze[neighbor], 0)

                    if new_score > dp_scores[neighbor]:
                        dp_scores[neighbor] = new_score
                        predecessors[neighbor] = (r, c)
                        new_visited_path = visited_path.copy()
                        new_visited_path.add(neighbor)
                        # Push the new, better path onto the priority queue
                        heapq.heappush(pq, (-new_score, neighbor, new_visited_path))

        best_target_pos, max_total_score = None, -float('inf')

        for r in range(self.rows):
            for c in range(self.cols):
                if self.maze[r, c] == EXIT and dp_scores[r, c] > -float('inf'):
                    cell = (r, c)
                    path_score = dp_scores[cell]
                    total_score = path_score + self.exit_bonus

                    if total_score > max_total_score:
                        max_total_score = total_score
                        best_target_pos = cell

        if not best_target_pos: return [], 0

        path = []
        curr = best_target_pos
        while curr is not None:
            path.append(curr)
            curr = predecessors.get(curr)
        path.reverse()

        return path, max_total_score